package liangtWorkSpace.suanfa;

/**
 * 希尔排序
 *      局部排序在整体排序 -- 依赖插入排序 -- 插入排序的优化
 *      序列优化 -- Knuth序列
 *      arrays.length =
 */
public class ShellSort {

    /**
     * 排序
     */
    public static void sort(int[] arrs){
        int h = 1;
        while (h <= arrs.length / 3){
            h = h*3 +1;
        }
        System.out.println(h);
        for (int gap = 4;gap > 0; gap=(gap - 1)/3){
            for (int i = 1; i < arrs.length; i++) {
                for (int j = i; j >0 && arrs[j] < arrs[j-1]; j-=gap) {
                    SortUtils.swap(j,j-1,arrs);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arrs = SortUtils.getArrays(15);
        SortUtils.print(arrs);
        sort(arrs);
        System.out.println();
        SortUtils.print(arrs);
    }

}
